package Hot100;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-12-26 13:19
 */
public class maximalRectangle85 {

    /**85. 最大矩形
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     * 对每个元素计算其左边连续最多的1的个数，然后每一列最为一个柱状图，调用《84. 柱状图中最大的矩形》的方法求出最大矩形
     * */
    public int maximalRectangle(char[][] matrix) {
        int m=matrix.length;
        if (m==0) return 0;
        int n=matrix[0].length;
        int[][] left=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]=='1'){
                    left[i][j]=(j==0?0:left[i][j-1])+1;
                }
            }
        }
        int res=0;
        for (int j = 0; j < n; j++) {
            //对每一列调用柱状图中的最大矩形
            int[] heights=new int[m];
            for (int i = 0; i < m; i++) {
                heights[i]=left[i][j];
            }
            res =Math.max(res,largestRectangleArea(heights));
        }
        return res;
    }
    public int largestRectangleArea(int[] heights) {
        int n=heights.length;
        int res=0;
        int[] left=new int[n];
        int[] right=new int[n];
        //单调栈：
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < n; i++) {
            //从左向右记录i之前第一个比i小的位置
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            left[i]=(stack.isEmpty()?-1:stack.peek());
            stack.push(i);
        }
        stack.clear();
        for (int i = n-1; i >=0; i--) {
            //从右向左记录i之后第一个比i小的位置
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i]=(stack.isEmpty()?n:stack.peek());
            stack.push(i);
        }
        for (int i = 0; i < n; i++) {
            //通过前面的比i大于等于的个数到i后面比i大于等于的个数，得到i的最大面积
            res=Math.max(res,(right[i]-left[i]-1)*heights[i]);
        }
        return res;
    }
}
